<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <script>
        function TreeNode(val) {
            this.val = val;
            this.left = null;
            this.right = null;
        }
        // a是根节点
        var a = new TreeNode(3);
        var b = new TreeNode(0);
        var c = new TreeNode(2);
        var f = new TreeNode(4);
        var g = new TreeNode(1);
        var h = new TreeNode(5);
        a.left = b;
        a.right = f;
        b.right = c;
        c.left = g;
        f.left = h
        var sortedArrayToBST = function (nums) {
            debugger
            // 1. 声明变量
            let nodeQueue = [] // 存放节点
            let leftQueue = [] // 存放左区间的下标
            let rightQueue = [] // 存放右区间的下表
            let root = new TreeNode(0) // 初始化根节点
            nodeQueue.push(root)
            leftQueue.push(0)
            rightQueue.push(nums.length - 1)

            // 2. 进行while循环
            while (nodeQueue.length !== 0) {
                debugger
                let curNode = nodeQueue.shift()
                let left = leftQueue.shift()
                let right = rightQueue.shift()
                let mid = left + Math.floor((right - left) / 2)
                curNode.val = nums[mid]

                // 处理左节点
                if (left <= mid - 1) {
                    curNode.left = new TreeNode(0)
                    nodeQueue.push(curNode.left)
                    leftQueue.push(left)
                    rightQueue.push(mid - 1)
                }


                // 处理右节点
                if (right >= mid + 1) {
                    curNode.right = new TreeNode(0)
                    nodeQueue.push(curNode.right)
                    leftQueue.push(mid + 1)
                    rightQueue.push(right)
                }
            }
            return root
        };
        console.log(sortedArrayToBST([-10, -3, 0, 5, 9]));
    </script>
</body>

</html>